原题链接:POJ 2723 Get Luffy Out
题目大意:一共有对钥匙和个门,每个门上有两把锁,只要开了其中一把就可以往下一层.锁是按顺序给出的,也必须按顺序开.其次,每对钥匙如果用了其中一个,另外一个就不能用.一开始你在第层,门在两层之间,问你最多能开多少扇门.
注意:钥匙只有在配对的另一个用了之后才不能用,一个钥匙本身是可以多次开门的
数据范围:
把门看做物品的话,可以发现每扇门都是必须要开的,并且有一个二元关系:即必须在两个锁之间开一个.由此可以想到使用解决这个问题.不过由于题目问的是最多开多少个门,所以答案不是简单的建图再直接输出.简朴的暴力思想就是枚举每一扇门,但是可以发现由于门都是必须连续开的,也就是说开多少扇门是有单调性的,进而可以二分确定.
私以为网上看到的题解大部分没说明二分的判据和建图过程,这是非常要不得的,某些题解虽然过了,不过感觉有二分区间上的问题,可能要加一减一之类的操作,很怪.
考虑二分框架:每次判断个门能不能过掉,开始先把的个门建出来,再通过判断是否是合法的,如果是合法的区间右移,由于也可能是答案,所以,反之,,因为必然不是答案,让之后可以一直往前推到,因此可以覆盖所有情况.实际的代码框架见下:
注意建图过程是在里的.
int l = 0,r = m;
while(l < r)
{
int mid = l + r + 1 >> 1;
if(check(mid)) l = mid;
else r = mid - 1;
}
之后考虑建图,建图的套路就是找一个选择和另外一个必须的选择.对于一个门来说,因为他必须要选一个,考虑以下两种情况:
①在用了左边的钥匙之后,左边钥匙配对的那个就不能用了,这是题目给的限制条件.这里得考虑把他变成一个必须条件:逆向考虑就可以了.假如说我选了左边钥匙的配对的那一把,则我不能再选左边那把钥匙了,我只能选右边那个门对应的钥匙.转换一下就是,如果我选了左边钥匙的配对钥匙,则我必须选择右边的那扇门,因为我左边的钥匙因为选了配对钥匙的原因被损坏了.这就是一个必须关系.
另外一个关系对称的来就行了,如果我选了右边钥匙的配对钥匙,则右边钥匙必不能选,我只能选左边的,因此就是右边钥匙的配对钥匙去连左边的钥匙.
具体建图的内容可以看代码,因为这个东西不太好描述,看代码建图还是直接一点.
代码:
#define _CRT_SECURE_NO_WARNINGS
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <queue>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
const int N = 1e5+7,M = 1e5+7;
int time_stamp,dfn[N],low[N];
int n,m;
int edge[M],succ[M],ver[N],idx;
int stk[N],top;
bool in_stk[N];
int id[N],scc_cnt,siz[N];
int op[N],p[N],q[N];
void add(int u,int v)
{
edge[idx] = v;
succ[idx] = ver[u];
ver[u] = idx++;
}
void tarjan(int u)
{
dfn[u] = low[u] = ++time_stamp;
stk[++top] = u,in_stk[u] = 1;
for(int i = ver[u];~i;i = succ[i])
{
int j = edge[i];
if(!dfn[j])
{
tarjan(j);
low[u] = min(low[u],low[j]);
}
else if(in_stk[j])
low[u] = min(low[u],dfn[j]);
}
if(dfn[u] == low[u])
{
int y;
++scc_cnt;
do
{
y = stk[top--];
in_stk[y] = 0;
id[y] = scc_cnt;
siz[scc_cnt]++;
}while(y != u);
}
}
bool check(int lim)
{
memset(ver,-1,sizeof ver);
memset(dfn,0,sizeof dfn);
idx = 0;top = 0;time_stamp = 0;scc_cnt = 0;
memset(in_stk,0,sizeof in_stk);
memset(low,0,sizeof low);
for(int i = 0;i < lim;++i)
{
int u = p[i],v = q[i];
add(op[u],v);
add(op[v],u);
}
for(int i = 0;i < 2 * n;++i)
if(!dfn[i])
tarjan(i);
for(int i = 0;i < n;++i)
if(id[i] == id[op[i]])
return 0;
return 1;
}
int main()
{
while(scanf("%d%d",&n,&m),n || m)
{
for(int i = 1;i <= n;++i)
{
int u,v;scanf("%d%d",&u,&v);
op[u] = v;
op[v] = u;
}
for(int i = 0;i < m;++i) scanf("%d%d",&p[i],&q[i]);
int l = 0,r = m;
while(l < r)
{
int mid = l + r + 1 >> 1;
if(check(mid)) l = mid;
else r = mid - 1;
}
printf("%d\n",l);
}
return 0;
}